package 链表;

/**
 * https://leetcode.cn/problems/add-two-numbers/description/
 * 两数相加
 */
public class ListNode {


    int val;
    ListNode next;
    ListNode prev;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    /**
     * k个一组进行翻转
     * https://leetcode.cn/problems/reverse-nodes-in-k-group/
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        // 找到链表的长度
        while (head != null) {
            head = head.next;
            n++;
        }
        // 要分多少组, prev 是替死鬼
        n = n / k;
        ListNode newHead = new ListNode(0), prev = newHead;
        newHead.next = head;
        // 循环 n 次
        while(n-- != 0) {
            // 长度为 k 的链表进行逆序, 头插法
            int t = k; // 替死
            ListNode tmp = head;  // 用于标记下一次头插的地方
            while(t-- != 1) {
                ListNode headNext = head.next;
                // 头插
                head.next = prev.next;
                prev.next = head;
                // 走下一步
                head = headNext;
            }
            prev = tmp; // 更新下一次头插的地方
        }
        // 循环走完, 把后面的直接连到主链表后面
        prev.next = head;
        return newHead.next;
    }

    /**
     * 两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 模拟相加过程. 定义一个虚拟头结点
        ListNode newHead = new ListNode(-1);
        // 替死鬼
        ListNode cur = newHead;
        int tmp = 0; // 进位数
        while(l1 != null || l2 != null || tmp != 0) {
            // 相加, 有非空条件
            if(l1 != null) {
                tmp += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                tmp += l2.val;
                l2 = l2.next;
            }
            // 把结果串在新节点的后面. 假如tmp 是 12. 串的话就是2
            cur.next = new ListNode(tmp % 10);
            cur = cur.next;
            tmp /= 10;
        }
        return newHead.next;
    }


    // 翻转链表: https://leetcode.cn/problems/UHnkqh/description/
    public ListNode reverseList(ListNode head) {

        // 创建一个虚拟头结点, 一定要有值, 不然就会空指针
        ListNode newHead = new ListNode(0);

        while(head != null) {
            // 记录下一个值
            ListNode nextNode = head.next;

            // 头插，先连接后面的节点， 再绑定前面的节点
            head.next = prev.next;
            prev.next = head;

            head = nextNode;
        }
        return newHead.next;
    }


}
